#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	enum presence {zero, one, dont};
	int n, C;          // ����� ��������� � ������������ ���
	cin >> n >> C;
	vector<int> c(n), w(n);   // ��������� ��������� � �� ����
	for (int i = 0; i < n; ++i) {
		cin >> c[i] >> w[i];
	}
	deque<vector<presence>> queue;
	int record = 0;
	vector<presence> cur(n, dont);
	queue.push_back(cur);
	while (!queue.empty()) {
		cur = queue.front();
		queue.pop_front();
		cout << "�����:" << endl;
		for(int i = 0; i < n; ++i) {
			if (cur[i] == zero) cout << "0 ";
			else if (cur[i] == one) cout << "1 ";
			else cout << "_ ";
		}
		cout << endl;
		
		int cur_record = 0, cur_weight = 0;
		for (int i = 0; i < n; ++i) {
			if (cur[i] == one) {
				cur_record += c[i];
				cur_weight += w[i];
			}
		}
		if (cur_weight > C) {
			cout << "��������� ��� ��������� �����������" << endl;
			continue;
		}
		int s = 0;
		while (s < n && C - cur_weight >= 0) {
			if (cur[s] == dont) {
				cur_weight += w[s];
				cur_record += c[s];
			}
			s += 1;
		}
		--s;
		if (C - cur_weight < 0) {
			cur_weight -= w[s];
			cur_record -= c[s];
		} else {
			if (cur_record > record) {
				record = cur_record;
			}
			cout << "��� ���������� �������� ����� � �����" << endl;
			continue;
		}
		cout << "������� ����������: " << s+1 << endl;
		cout << "������� ���: " << cur_weight << endl;
		cout << "������� ������: " << cur_record << endl;
		double ULR = cur_record + double(c[s])/w[s]*(C-cur_weight);
		if (cur_record > record) {
			record = cur_record;
		}
		if (ULR < record) {
			cout << "������� ������ ULR ������ �������������: " << ULR << "<" << record << endl; 
			continue;
		}
		vector<presence> task1 = cur, task2 = cur;
		task1[s] = zero;
		task2[s] = one;
		queue.push_back(task1);
		queue.push_back(task2);
	}
	cout << record << endl;
	return 0;
}

//2 5
//7 4
//3 6
//c[0] = 7, c[1] = 3
//w[0] = 4, w[0] = 6
//�� ���� ������� ������� ���� �������� 1 ����� ��� ���, ����� ���� �������� 2 � ��� ���